1. Technical Field
The present invention relates generally to an improved graphics subsystem and in particular to a method and an apparatus for processing binary space partitioning (BSP) trees. Still more particularly, the present invention provides a method and an apparatus for improving the accuracy of the bounding volumes for BSP-trees.
2. Description of the Related Art
The display of three dimensional graphic images of complex scenes in real time have improved greatly as hardware and software have improved. These images are very complex, so efficient processing is of utmost importance. Binary space partitioning (BSP) trees were introduced in the early 1980""s (See Fuchs, Kedem, and Nayor xe2x80x9cOn Visible Surface Generation by A Priori Tree Structuresxe2x80x9d, SIGGRAPH ""80, pp. 124-133, the content of which is hereby incorporated by reference for all purposes) to aid in the processing of 3-D scenes.
BSP trees are a standard tool in image processing and are continually being improved through refinement. A BSP tree divides an n-dimensional space into two components using an n-1 dimensional object. For example, a 0 dimensional point on a line divides the 1 dimensional line into two components. Alternatively, a 1 dimensional line divides a 2 dimensional plane into two components. For a 3 dimension scene, a 2 dimensional plane divides the scene into two components.
The process of subdivision continues recursively to subdivide an n-dimensional space into smaller components called polytopes. A polytope is a generalization of a polyhedron. Informally, it is a multi-dimensional solid with flat sides. The faces are the hyper-planes that are subdividing the n-dimensional space. Storing these polytopes in a BSP tree allows the n-dimensional space to be classified and sorted in a manner that assists in carrying out other processing tasks, such as hidden surface removal.
Polytopes can approximate objects in the n-dimensional space. Therefore, it would be advantageous to have improved bounding volumes in a BSP tree to make graphics processing more accurate.
The present invention provides a method, system, and computer program product for reducing a boundary of a subspace in a binary space partitioning tree. In one embodiment a space containing an object for which an image is to be rendered and displayed to a user is divided into subspaces. The boundaries of each subspace are recalculated to remove at least a portion of the dead space from within the subspace. The recalculation is performed by analyzing the spatial extent of the object or objects within the each subspace and recalculating the boundaries of each subspace to be coextensive with the boundaries of the object or objects within the subspace.